<?php

/**
 * @see Zend_Filter_Interface
 */
require_once 'Zend/Filter/Interface.php';


/**
 * Polyline GMap
 *
 * @category   Core
 * @package    Core_Filter_Google_Maps
 * @link       http://www.fonant.com/demos/douglas_peucker/algorithm
 * @license    This software is provided as-is, with no warranty. Please use and modify freely for anything you like :)
 * @copyright  Copyright (c) 2008 Kuśmierz Adam
 * @author     Anthony Cartmell ajcartmell@fonant.com
 * @version    Version 1.1 - 17 Jan 2007  (fixes nasty bug!)
 */

class Core_Filter_Google_Maps_PolylineReducer implements Zend_Filter_Interface
{
	protected $_original_points = array();
	protected $_include_points = array();
	protected $_tolerance;
	protected $_tolerance_squared;
	
	/**
	 * Contstruct
	 *
	 * @param float $tolerance
	 */
	public function __construct($tolerance = 0.5)
	{
		$this->setTolerance($tolerance);
	}
	
	/**
	 * Setting tolerance
	 *
	 * @param float $tolerance
	 * @return Core_Filter_Google_Maps_PolylineReducer
	 */
	public function setTolerance($tolerance)
	{
		if (!is_numeric($tolerance))
			return false;
		
		$this->_tolerance_squared = $tolerance * $tolerance;
		$this->_tolerance = floatval($tolerance);
		
		return $this;
	}
	
	/**
	 * Getting tolerance value
	 *
	 * @return float
	 */
	public function getTolerance()
	{
		return $this->_tolerance;
	}
	
	/**
	 * Defined by Zend_Filter_Interface
	 *
	 * Returns a list of GeoPoints for the simplest polyline that leaves
	 * no original point more than $tolerance away from it.
	 *
	 * @param  array $value
	 * @return array
	 */
	public function filter($points)
	{
		$this->_original_points = $this->_include_points = array();
		
		foreach ($points as $point) {
			if (!isset($point['x']) || !isset($point['y']))
				return false;
		}
		$this->_original_points = $points;
		
		// Include first and last points
		$this->_include_points[0] = true;
		$this->_include_points[count($this->_original_points) - 1] = true;
		
		$this->_douglasPeucker(0, count($this->_original_points) - 1);
		$out = array();
		ksort($this->_include_points);
		foreach ($this->_include_points as $key => $point) {
			$out[] = $this->_original_points[$key];
		}
		
		return $out;
	}

	/**
	 * Douglas-Peuker polyline simplification algorithm. First draws single line
	 * from start to end. Then finds largest deviation from this straight line, and if
	 * greater than tolerance, includes that point, splitting the original line into
	 * two new lines. Repeats recursively for each new line created.
	 *
	 * @param int $start_vertex_index
	 * @param int $end_vertex_index
	 */
	protected function _douglasPeucker($start_vertex_index, $end_vertex_index)
	{
		if ($end_vertex_index <= $start_vertex_index + 1) // there is nothing to simplify
			return false;

		// Make line from start to end
		$line = array($this->_original_points[$start_vertex_index], $this->_original_points[$end_vertex_index]);
		
		// Find largest distance from intermediate points to this line
		$max_dist_to_line_squared = 0;
		for ($index = $start_vertex_index + 1; $index < $end_vertex_index - 1; $index ++)
		{
			$dist_to_line_squared = $this->_distanceToPointSquared($line, $this->_original_points[$index]);
			
			if ($dist_to_line_squared > $max_dist_to_line_squared) {
				$max_dist_to_line_squared = $dist_to_line_squared;
				$max_dist_index = $index;
			}
		}
		
		// Check max distance with tolerance
		if ($max_dist_to_line_squared > $this->_tolerance_squared) {        // error is worse than the tolerance
			// split the polyline at the farthest vertex from S
			$this->_include_points[$max_dist_index] = true;
			// recursively simplify the two subpolylines
			$this->_douglasPeucker($start_vertex_index, $max_dist_index);
			$this->_douglasPeucker($max_dist_index, $end_vertex_index);
		}
		// else the approximation is OK, so ignore intermediate vertices
	}
	
	protected function _distanceToPointSquared($line, $point)
	{
		$v = array('x' => $point['x'] - $line[0]['x'], 'y' => $point['y'] - $line[0]['y']);
		$l = array('x' => $line[1]['x'] - $line[0]['x'], 'y' => $line[1]['y'] - $line[0]['y']);
		
		$magnitude = sqrt($l['x'] * $l['x'] + $l['y'] * $l['y']);
		if ($magnitude == 0)
			$l = array('x' => 0, 'y' => 0);
		else
			$l = array('x' => $l['x']/$magnitude, 'y' => $l['y']/$magnitude);
		
		$dot = ($l['x'] * $v['x'] + $l['y'] * $v['y']);
		
		if ($dot <= 0) { // Point nearest P1
			$dl = array($line[0], $point);
			return $this->_lengthSquared($dl);
		}
		if (($dot*$dot) >= $this->_lengthSquared($line)) { // Point nearest P2
			$dl = array($line[1], $point);
			return $this->_lengthSquared($dl);
		} else { // Point within line
			$v2 = array($line[0], $point);
			$h = $this->_lengthSquared($v2);
			return $h - $dot * $dot;
		}
	}
	
	protected function _lengthSquared($line)
	{
		$dx = $line[0]['x'] - $line[1]['x'];
		$dy = $line[0]['y'] - $line[1]['y'];
		return $dx * $dx + $dy * $dy;
	}
}